package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 第 N 个泰波那契数
        Solution solution1 = new Solution();
        System.out.println("第 N 个泰波那契数:");
        System.out.println("tribonacci(4) = " + solution1.tribonacci(4)); // 4
        System.out.println("tribonacci(25) = " + solution1.tribonacci(25)); // 1389537

        // 测试用例 - 三步问题
        Solution2 solution2 = new Solution2();
        System.out.println("\n三步问题:");
        System.out.println("waysToStep(3) = " + solution2.waysToStep(3)); // 4
        System.out.println("waysToStep(5) = " + solution2.waysToStep(5)); // 13
    }

    // 第 N 个泰波那契数
    static class Solution {
        public int tribonacci(int n) {
            // 边界情况处理
            if (n == 0) return 0;
            if (n == 1 || n == 2) return 1;

            // 创建dp数组
            int[] dp = new int[n + 1];

            // 初始化前三项
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;

            // 递推计算
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            }

            return dp[n];
        }
    }

    // 三步问题
    static class Solution2 {
        public int waysToStep(int n) {
            // 边界处理
            if (n == 1) return 1;
            if (n == 2) return 2;

            long[] dp = new long[n + 1];
            int MOD = 1000000007;

            // 初始化
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;

            // 递推计算，边算边取模
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
            }

            return (int) dp[n];
        }
    }
}